package 中等.脑筋急转弯;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums，和一个整数 k 。
 * 对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。
 * nums 的 分数 是 nums 中最大元素和最小元素的差值。
 * 在更改每个下标对应的值之后，返回 nums 的最小 分数 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/smallest-range-ii
 */
public class 最小差值II_910 {

    public static void main(String[] args) {

        System.out.println(smallestRangeII(new int[]{7, 8, 8}, 5));

    }

    /**
     * 1，将数组排序
     * 2，遍历数组，遍历到索引 i 时 ，将 [0,i] 全部向上 +k
     * [i+1,len-1] 全部向下 -k
     * 此时，最大值只可能是 nums[i]+k 或者 nums[len-1]-k
     * 最小值只可能是 nums[0]+k 或者 nums[i+1]-k
     */
    public static int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);

        // 将所有点全部向上移或者向下移动也是一种策略
        int minScore = nums[nums.length - 1] - nums[0];

        // 部分前面的点向上移动，后面的点向下移动
        for (int i = 0; i < nums.length - 1; i++) {
            int max = Math.max(nums[i] + k, nums[nums.length - 1] - k);
            int min = Math.min(nums[0] + k, nums[i + 1] - k);

            minScore = Math.min(minScore, max - min);
        }

        return minScore;
    }

}
